package org.liaohailong.helloworld.study;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;

/**
 * Author: liaohailong
 * Time: 2021/5/10 17:50
 * Describe:
 */
public class StackSolution {


    //    输入：s = "3[a2[c]]"
    //    输出："accaccacc"
    //    输入：s = "2[abc]3[cd]ef"
    //    输出："abcabccdcdcdef"
    public String decodeString(String s) {
        Stack<Integer> nums = new Stack<>();
        LinkedList<String> list = new LinkedList<>();
        LinkedList<String> result = new LinkedList<>();

        Stack<String> tempS = new Stack<>();

        int opCount = 0;
        for (int i = 0; i < s.length(); i++) {
            String one = String.valueOf(s.charAt(i));

            if (isNumber(one)) {
                int endIndex = findNum(s, i);
                String num = s.substring(i, endIndex + 1);
                nums.push(Integer.parseInt(num));
                i = endIndex;
            } else {
                if ("[".equals(one)) {
                    list.addLast(one);
                    opCount++;
                } else if ("]".equals(one)) {
                    tempS.clear();
                    while (!"[".equals(list.peekLast())) tempS.push(list.pollLast());
                    list.pollLast();// pick "[" out of stack
                    opCount--;

                    StringBuilder sb = new StringBuilder();
                    while (!tempS.isEmpty()) sb.append(tempS.pop());
                    // times to add
                    int times = nums.pop();
                    for (int j = 0; j < times; j++) {
                        if (opCount > 0)
                            list.addLast(sb.toString());
                        else
                            result.addLast(sb.toString());
                    }

                } else {
                    if (opCount > 0)
                        list.addLast(one);
                    else
                        result.addLast(one);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (String one : result) {
            sb.append(one);
        }
        return sb.toString();
    }


    private boolean isNumber(String s) {
        boolean ok = false;
        switch (s) {
            case "0":
            case "1":
            case "2":
            case "3":
            case "4":
            case "5":
            case "6":
            case "7":
            case "8":
            case "9":
                ok = true;
                break;
        }
        return ok;
    }

    private int findNum(String str, int beginIndex) {
        int endIndex = beginIndex;
        for (int i = beginIndex; i < str.length(); i++) {
            String one = String.valueOf(str.charAt(i));
            if (isNumber(one)) {
                endIndex = i;
                continue;
            }
            break;
        }
        return endIndex;
    }


    // LC 图像渲染
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor == newColor) return image;
        floodFill(image, sr, sc, oldColor, newColor);
        return image;
    }


    private void floodFill(int[][] image, int ax, int ay, int oldColor, int newColor) {
        // out of bounds
        if (ax < 0 || image.length <= ax || ay < 0 || image[ax].length <= ay) return;

        int mineColor = image[ax][ay];
        if (mineColor == oldColor) {
            image[ax][ay] = newColor;

            // up
            floodFill(image, ax, ay - 1, oldColor, newColor);
            // down
            floodFill(image, ax, ay + 1, oldColor, newColor);
            // left
            floodFill(image, ax - 1, ay, oldColor, newColor);
            // right
            floodFill(image, ax + 1, ay, oldColor, newColor);
        }
    }

    public int[][] updateMatrix(int[][] mat) {
        int target = 0;
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                updateMatrix(mat, i, j, target);
            }
        }
        return mat;
    }

    public void updateMatrix(int[][] mat, int ax, int ay, int target) {
        // out of bounds
        if (ax < 0 || mat.length <= ax || ay < 0 || mat[ax].length <= ay) return;

        // target is himself
        int val = mat[ax][ay];
        if (val == target) return;

        Set<Point> visitor = new HashSet<>();
        LinkedList<Point> bfs = new LinkedList<>();
        bfs.add(new Point(ax, ay));
        int depth = 0;
        while (!bfs.isEmpty()) {
            int size = bfs.size();
            depth++;
            while (size-- > 0) {
                Point node = bfs.pollFirst();
                if (node == null) continue;

                // avoid traversal same point twice
                if (visitor.contains(node)) continue;
                visitor.add(node);

                boolean find;
                Point next;
                // up
                next = new Point(node.x - 1, node.y);
                find = _findTarget(mat, next, target);
                if (find) {
                    bfs.clear();
                    break;
                } else {
                    if (isInBounds(mat, next.x, next.y)) bfs.addLast(next);
                }
                // down
                next = new Point(node.x + 1, node.y);
                find = _findTarget(mat, next, target);
                if (find) {
                    bfs.clear();
                    break;
                } else {
                    if (isInBounds(mat, next.x, next.y)) bfs.addLast(next);
                }
                // left
                next = new Point(node.x, node.y - 1);
                find = _findTarget(mat, next, target);
                if (find) {
                    bfs.clear();
                    break;
                } else {
                    if (isInBounds(mat, next.x, next.y)) bfs.addLast(next);
                }
                // right
                next = new Point(node.x, node.y + 1);
                find = _findTarget(mat, next, target);
                if (find) {
                    bfs.clear();
                    break;
                } else {
                    if (isInBounds(mat, next.x, next.y)) bfs.addLast(next);
                }
            }
        }

        mat[ax][ay] = depth;
    }

    public boolean _findTarget(int[][] mat, Point point, int target) {
        // out of bounds
        if (!isInBounds(mat, point.x, point.y)) return false;

        return mat[point.x][point.y] == target;
    }

    private boolean isInBounds(int[][] mat, int ax, int ay) {
        return ax >= 0 && mat.length > ax && ay >= 0 && mat[ax].length > ay;
    }

    private static final class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }


    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        if (rooms.isEmpty()) return true;

        // first room
        List<Integer> integers = rooms.get(0);

        // first room no keys?
        if (integers.isEmpty()) return rooms.size() == 1;

        // record rooms
        Set<Integer> visitor = new HashSet<>();
        visitor.add(0);

        // bfs
        LinkedList<Integer> bfs = new LinkedList<>(integers);

        while (!bfs.isEmpty()) {
            Integer key = bfs.pollFirst();
            if (key == null) continue;

            // avoid enter the same room twice
            if (visitor.contains(key)) continue;

            // record room to visitor
            visitor.add(key);

            List<Integer> keys = rooms.get(key);
            bfs.addAll(keys);
        }

        // check all room visited
        return visitor.size() == rooms.size();
    }
}
